package com.lihepeng.leecode.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums，请你将该数组升序排列。
 * 使用快速排序
 */
public class Solution912 {
    public int[] sortArray(int[] nums) {
        quickSort(0,nums.length-1,nums);
        return nums;
    }

    /**
     * 堆排序
     * 构建大碓顶 然后将下面的元素替换头部元素
     */
    private void heapSort(int nums){
        buildMaxHeap(nums);
    }

    /**
     * 构建大碓顶
     * @param nums
     */
    private void buildMaxHeap(int nums) {

    }


    private void quickSort(int low,int high,int[]nums){
        if (low>=high) {
            return;
        }

        int left = low;
        int right = high;
        int provit = nums[left];


        while (left < right) {
            while (left<right && nums[right]>=provit) {
                right --;

            }
            nums[left] = nums[right];
            while (left <right && nums[left]<=provit){
                left ++;
            }
            nums[right] = nums[left];
        }
        nums[left] = provit;
        quickSort(low,right-1,nums);
        quickSort(right+1,high,nums);
    }
    @Test
    public void runTest(){
        int[] arrs = {1,5,2,3,6,4};
        int[] ints = sortArray(arrs);
        System.out.println(Arrays.toString(ints));
    }
}
